package com.zh.note.huawei.onehundred.求符合条件元组个数;

import java.util.*;

/**
 * https://dream.blog.csdn.net/article/details/131158605
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // String input = sc.nextLine();
        // int[] nums = Arrays.stream(input.split(" ")).mapToInt(Integer::parseInt).toArray();
        // int k = sc.nextInt();
        // int target = sc.nextInt();
        int[] nums = {-1, 0, 1, 2, -1, -4, -1};
        int k = 3;
        int target = 0;
        //
        // int[] nums = {2, 7, 11, 15};
        // int k = 2;
        // int target = 9;

        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        //必须排序
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        dsf(nums, 0, 0, k, target, path, res, used);
        System.out.println(res);
        System.out.println(res.size());
    }
    // 组合之和，去重
    private static void dsf(int[] nums, int startIndex, int sum, int k, int target, Deque<Integer> path, List<List<Integer>> res, boolean[] used) {
        if (sum > target) {
            return;
        }
        if (path.size() == k && sum == target) {
            res.add(new ArrayList<>(path));
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { //去重
                continue;
            }
            sum += nums[i];
            path.add(nums[i]);
            used[i] = true;
            dsf(nums, i + 1, sum, k, target, path, res, used);
            used[i] = false;
            path.removeLast();
            sum -= nums[i];
        }
    }
}
